﻿/* Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia). */




using System;
using System.Text.RegularExpressions;

class QuickSort
{
    static void Main()
    {
        uint N;
        bool iProvided = false;

        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer (>0).");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);

        iProvided = false; //reset iProvided
        string[] inputStringA = new string[N];
        for (int i = 0; i < inputStringA.Length; i++)
        {
            iProvided = false;
            do
            {
                if (iProvided == true) Console.WriteLine("Error!: only letters and simple numbers are allowed (a-z, A-Z, 0-9*): ");
                else iProvided = true;
                Console.Write("Enter a word: ");
                inputStringA[i] = Console.ReadLine();
            } while (!Regex.IsMatch(inputStringA[i], @"^[a-zA-Z0-9]+$"));
        }
        
        string[] inputStringA_S = (string[])inputStringA.Clone(); //clone a copy

        Q_Sort(inputStringA_S, 0, inputStringA_S.Length-1);

        for (int i = 0; i < inputStringA_S.Length; i++) Console.WriteLine(inputStringA_S[i]);

        Console.WriteLine();
    }

    /* Method to sort strings using the QuickSort algo */
    /* EXCLUSIVELY ALTERED BY ME:) TO HANDLE STRINGS */
    private static void Q_Sort(string[] arr, int left, int right)
    {
        int i = left;
        int j = right;
        string leftString = arr[i];
        string rightString = arr[j];
        double pivotV = ((left+right)/2);

        string mid = arr[Convert.ToInt32(pivotV)];
        string temp = null;
        while (i <= j)
        {
            while (arr[i].CompareTo(mid) < 0)
            {
                i++;
                leftString = arr[i];
            }
            while (arr[j].CompareTo(mid) > 0)
            {
                j--;
                rightString = arr[j];
            }
            if (i <= j)
            {
                temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }
        if (left < j)
        {
            Q_Sort(arr, left, j);
        }
        if (i < right)
        {
            Q_Sort(arr, i, right);
        }
    }
}
